import java.util.*;

/**
 * 邻接矩阵
 * 一维数组+二维数组
 * 一维数组存储定点
 * 二维数组存储权值
 */
public class GraphByMatrix {
    private char[] arrayV;// 存放定点
    private int[][] matrix;// 存放矩阵的权值
    private boolean isDirect;// 判断是有向图还是无向图

    public GraphByMatrix(int size, boolean isDirect) {
        this.arrayV = new char[size];
        this.matrix = new int[size][size];
        for (int i = 0; i < size; i++) {
            Arrays.fill(matrix[i], Integer.MAX_VALUE);
        }
        this.isDirect = isDirect;
    }

    /**
     * // 初始化定点数组
     *
     * @param arrayV 以后的定点数组
     */
    public void insertArrayV(char[] arrayV) {
        for (int i = 0; i < arrayV.length; i++) {
            this.arrayV[i] = arrayV[i];
        }
    }

    /**
     * 插入边，刚更新权值
     * @param srcV   起点顶点
     * @param destV  终点顶点
     * @param weight 权值
     */
    public void addEdge(char srcV, char destV, int weight) {
        // 获取起点和终点的下标
        int src = getIndex(srcV);
        int dest = getIndex(destV);
        // 更新启动和终点的在矩阵的权值
        matrix[src][dest] = weight;
        // 如果是无向图，那 起点-》终点 和 终点-》起点 的权值都需要更新
        if (!isDirect) {
            matrix[dest][src] = weight;
        }
    }

    /**
     * 获取定点在数组的下标
     *
     * @return 顶点在顶点数组下标
     */
    private int getIndex(char srcV) {
        for (int i = 0; i < arrayV.length; i++) {
            if (arrayV[i] == srcV) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 获取定点的度
     * @param srcV 顶点
     */
    public int getDevOfV(char srcV) {
        int src = getIndex(srcV);
        int count = 0;
        for (int i = 0; i < arrayV.length; i++) {
            if (matrix[src][i] != Integer.MAX_VALUE) {
                count++;
            }
        }
        if (isDirect) {
            for (int i = 0; i < arrayV.length; i++) {
                if (matrix[i][src] != Integer.MAX_VALUE) {
                    count++;
                }
            }
        }
        return count;
    }
    /**
     * 遍历二维矩阵
     */
    private void printGraph() {
        System.out.print("  ");
        int len = arrayV.length;
        for(int i =0; i < len;i++) {
            System.out.print(arrayV[i] + " ");
        }
        System.out.println();
        for(int i =0; i < len;i++) {
            System.out.print(arrayV[i] + " ");
            for(int j = 0; j < len;j++) {
                if(matrix[i][j] == Integer.MAX_VALUE) {
                    System.out.print("* ");
                }else {
                    System.out.print(matrix[i][j] + " ");
                }

            }
            System.out.println();
        }
    }
    /**
     * 广度优先遍历
     * @param srcV 出发的顶点
     * 思想
     * 从一个定点出发，将这个定点放入一个队列中
     * 然后进入循环，将定点从队列中拿出，并且将以该点为顶点的边的终点放入到队列当中
     * visitedp 记录该定点是否被访问过，默认是 false 没有访问过
     * 在从队列中弹出一个点的时候将该点在visitedp对应的下标改为true 拿出的时候也改一次，防止某一个元素多次访问，直到队列为空
     */
    public void bfs(char srcV) {
        int len = arrayV.length;
        boolean[] visitedp = new boolean[len];
        Queue<Integer> queue = new LinkedList<>();
        int index = getIndex(srcV);
        queue.add(index);
        while(!queue.isEmpty()) {
            int n = queue.poll();
            //visitedp[n] = true;// 拿出的时候再一次 true
            System.out.print(arrayV[n] + " -> ");
            for(int i =0; i < len;i++) {
                if(matrix[n][i] != Integer.MAX_VALUE && !visitedp[i]) {
                    queue.add(i);
                    visitedp[i] = true;// 放入的时候改一次 true
                }
            }
        }
    }
    /**
     * 深度优先遍历
     * 从定点出发
     * 二维数组，查看遍历定点出去的边，并且把这个边在visitedp改成 true 当找到一条边没有访问过后，就递归
     * 去遍历该条边的终点这个定点出去的边
     * @param srcV 出发顶点
     */
    public void dfs(char srcV) {
        int index = getIndex(srcV);
        int len = arrayV.length;
        boolean[] visitedp = new boolean[len];
        dfsChild(index,visitedp,len);

    }
    private void dfsChild(int index, boolean[] visitedp,int len) {
        System.out.print(arrayV[index] + " ->");
        visitedp[index] = true;
        for(int i= 0; i < len;i++) {
            for(int j = 0; j < len;j++) {
                if(matrix[i][j] != Integer.MAX_VALUE && !visitedp[j]) {
                    dfsChild(j,visitedp,len);
                }
            }
        }
    }
    /**
     * Edge 是我们抽象出来的边
     */
    public class Edge {
        int srcIndex;// 起点
        int destIndex;// 终点
        int weigth;// 权值
        public Edge(int srcIndex, int destIndex, int weigth) {
            this.srcIndex = srcIndex;
            this.destIndex = destIndex;
            this.weigth = weigth;
        }
    }
    public int kruskal(GraphByMatrix minTree) {
        int len = arrayV.length; // 定点的个数
        // 构造一个小跟堆来存储边
        PriorityQueue<Edge> minQueue = new PriorityQueue<>(new Comparator<Edge>() {
            @Override
            public int compare(Edge o1, Edge o2) {
                return o1.weigth - o2.weigth;
            }
        });
        // 遍历邻接矩阵，将所有边存储到优先级队列当中
        for(int i = 0; i < len;i++) {
            for(int j =0; j < len;j++) {
                // 由于求最小生成树是无向图，无向图沿着对角线是一样的，所以只需要遍历邻接矩阵的一般即可
                if(i < j && matrix[i][j] != Integer.MAX_VALUE) {
                    // 把边存储到小跟对当中
                    minQueue.add(new Edge(i,j,matrix[i][j]));
                }
            }
        }
        // 创建一个并查集
        UnionFindSet ufs = new UnionFindSet(len);
        // 加下将边存储到我们的最小生成树当中
        int size = 0;// 统计已经添加到最小生成树当中的边的个数
        int count = 0;// 统计当前已经存储的边的权值和，最后返回权值和
        while(size < len - 1 && !minQueue.isEmpty()) {
            Edge edge = minQueue.poll();
            int srcIndex = edge.srcIndex;
            int destIndex = edge.destIndex;
            if(!ufs.isSameUnionFindSet(srcIndex,destIndex)) { // 判断是否是一个集合，不是一个集合就添加这条边
                size++;// 统计已经添加到最小生成树当中的边的个数
                count += matrix[srcIndex][destIndex];// 统计最小生成树权值
                ufs.union(srcIndex,destIndex);// 将起点和终点合并到并查集当中
                minTree.addEdgeUseIndex(srcIndex,destIndex,matrix[srcIndex][destIndex]);// 将边添加到最小生成树当中之中
                System.out.println("选择的边:" + arrayV[srcIndex] + "->" + ":" + matrix[srcIndex][destIndex]);
            }
        }
        if(size == len - 1) {
            return count;
        }else {
            return -1;
        }
    }
    private void addEdgeUseIndex(int srcIndex, int destIndex, int weight) {
        // 更新启动和终点的在矩阵的权值
        matrix[srcIndex][destIndex] = weight;
        // 如果是无向图，那 起点-》终点 和 终点-》起点 的权值都需要更新
        if (isDirect) {
            matrix[destIndex][srcIndex] = weight;
        }
    }
    public static void testGraphMinTree() {
        String str = "abcdefghi";
        char[] array = str.toCharArray();
        GraphByMatrix g = new GraphByMatrix(str.length(), false);
        g.insertArrayV(array);
        g.addEdge('a', 'b', 4);
        g.addEdge('a', 'h', 8);
        g.addEdge('a', 'h', 9);
        g.addEdge('b', 'c', 8);
        g.addEdge('b', 'h', 11);
        g.addEdge('c', 'i', 2);
        g.addEdge('c', 'f', 4);
        g.addEdge('c', 'd', 7);
        g.addEdge('d', 'f', 14);
        g.addEdge('d', 'e', 9);
        g.addEdge('e', 'f', 10);
        g.addEdge('f', 'g', 2);
        g.addEdge('g', 'h', 1);
        g.addEdge('g', 'i', 6);
        g.addEdge('h', 'i', 7);
        GraphByMatrix kminTree = new GraphByMatrix(str.length(),false);
        System.out.println(g.kruskal(kminTree));
        kminTree.printGraph();
    }

    /**
     * 迪杰斯科拉算法（求最短生成树）局部最小
     * 创建两个set 一个存储确定的点，应该存储不确定的点
     * 然后从不确定的set里选择一条最小的边，然后放入发哦
     * 出发定点vSrc出发，选择权值最小的边，直至确定的set当中，直到满足n-1
     *
     * @param minTree
     * @param chV
     * @return
     */
    public int prim(GraphByMatrix minTree,char chV) {
        int srcIndex = getIndex(chV);
        Set<Integer> setX = new HashSet<>();// 记录我们已经确定的点
        Set<Integer> setY = new HashSet<>();// 记录我们还未确定的点
        setX.add(srcIndex); // 将我们的起点放入到确定的集合当中
        int len = arrayV.length;
        // 初始化未确定点集合，将所有未确定的点放入到集合当中
        for(int i = 0; i < len;i++) {
            if(i != srcIndex) {
                setY.add(i);
            }
        }
        // 创建一个优先级队列（小跟堆）
        PriorityQueue<Edge> min = new PriorityQueue<>(new Comparator<Edge>() {
            @Override
            public int compare(Edge o1, Edge o2) {
                return o1.weigth - o2.weigth;
            }
        });
        // 将起点连接出去的边放入到优先级队列当中
        for(int i =0; i < len;i++) {
            if(matrix[srcIndex][i] != Integer.MAX_VALUE) {
                min.add(new Edge(srcIndex,i,matrix[srcIndex][i]));
            }
        }
        // 当前已经将起点连出去的边放入到了集合当中
        // 接下来遍历优先级队列，当setX数量到9时返回
        int count = 0;
        int size = 0;
        while(!min.isEmpty()) {
            Edge edge = min.poll();
            int srcI = edge.srcIndex;// 起点
            int dextI = edge.destIndex;// 终点
            if(setX.contains(dextI)) {
               // 如果dext 存在与setX当中 就不存储该条边，如果存储就好形成环路
                System.out.println("形成环路的边:" + arrayV[srcI] + "->" +arrayV[dextI]+ ":" + matrix[srcI][dextI]);
            }else {
                System.out.println("选择的边:" + arrayV[srcI] + "->" +arrayV[dextI]+ ":" + matrix[srcI][dextI]);
                minTree.addEdgeUseIndex(srcI,dextI,matrix[srcI][dextI]);// 将边放入到最小生成树当中
                size++;
                count += matrix[srcI][dextI];
                if(size == len - 1) {
                    return count;
                }
                for(int i = 0;i < len;i++) {
                    if(matrix[dextI][i] != Integer.MAX_VALUE && !setX.contains(i)) {
                        min.add(new Edge(dextI,i,matrix[dextI][i]));
                    }
                }
                setX.add(dextI);// 将终点放入到确定的集合中
                setY.remove(dextI);// 将终点从不确定的集合中删除
            }
        }
        return -1;
    }
    public static void testGraphMinTreePrim() {
        String str = "abcdefghi";
        char[] array =str.toCharArray();
        GraphByMatrix g = new GraphByMatrix(str.length(),false);
        g.insertArrayV(array);
        g.addEdge('a', 'b', 4);
        g.addEdge('a', 'h', 8);
        g.addEdge('a', 'h', 9);
        g.addEdge('b', 'c', 8);
        g.addEdge('b', 'h', 11);
        g.addEdge('c', 'i', 2);
        g.addEdge('c', 'f', 4);
        g.addEdge('c', 'd', 7);
        g.addEdge('d', 'f', 14);
        g.addEdge('d', 'e', 9);
        g.addEdge('e', 'f', 10);
        g.addEdge('f', 'g', 2);
        g.addEdge('g', 'h', 1);
        g.addEdge('g', 'i', 6);
        g.addEdge('h', 'i', 7);
        GraphByMatrix primTree = new GraphByMatrix(str.length(),false);
        System.out.println(g.prim(primTree,'a'));
        primTree.printGraph();
    }

    /**
     * 点s从Q当中选择一个最短的路径q，然后再松弛q当中的最短路径v 直到每一个点都访问过
     * @param vSrc 起点
     * @param dist 权值数组
     * @param pPath 关系数组
     */
    public void dijkstra(char vSrc, int[] dist, int[] pPath) {
        int srcIndex = getIndex(vSrc);

        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[srcIndex] = 0;

        Arrays.fill(pPath, -1);
        pPath[srcIndex] = 0;

        int len = arrayV.length;
        boolean[] s = new boolean[len];

        for (int k = 0; k < len; k++) {
            int min = Integer.MAX_VALUE;
            int u = -1;
            for (int i = 0; i < len; i++) {
                if (!s[i] && dist[i] < min) {
                    min = dist[i];
                    u = i;
                }
            }
            if (u == -1) {
                break; // 如果找不到可更新的节点，跳出循环
            }
            s[u] = true;
            for (int v = 0; v < len; v++) {
                if (!s[v] && matrix[u][v] != Integer.MAX_VALUE && dist[u] + matrix[u][v] < dist[v]) {
                    dist[v] = dist[u] + matrix[u][v];
                    pPath[v] = u;
                }
            }
        }
    }

    private void printShortPath(char s, int[] dist, int[] parentPath) {
        int srcIndex = getIndex(s);
        int len = arrayV.length;

        for(int i =0; i < len;i++) {
            if(i != srcIndex) {
                ArrayList<Integer> arrayList = new ArrayList<>();
                int pathI = i;
                while(pathI != srcIndex) {
                    arrayList.add(pathI);
                    pathI = parentPath[pathI];
                }
                arrayList.add(pathI);// 再add一次头结点
                Collections.reverse(arrayList);
                for(int pos:arrayList) {
                    System.out.print(arrayV[pos] +" -> ");
                }
                System.out.println(dist[i]);
            }
        }
    }
    public static void testGraphDijkstra() {
        String str = "syztx";
        char[] array = str.toCharArray();
        GraphByMatrix g = new GraphByMatrix(str.length(), true);
        g.insertArrayV(array);
        g.addEdge('s', 't', 10);
        g.addEdge('s', 'y', 5);
        g.addEdge('y', 't', 3);
        g.addEdge('y', 'x', 9);
        g.addEdge('y', 'z', 2);
        g.addEdge('z', 's', 7);
        g.addEdge('z', 'x', 6);
        g.addEdge('t', 'y', 2);
        g.addEdge('t', 'x', 1);
        g.addEdge('x', 'z', 4);
        int[] dist = new int[array.length];
        int[] parentPath = new int[array.length];
        g.dijkstra('s', dist, parentPath);

        g.printShortPath('s', dist, parentPath);
    }

    /**
     * 贝尔曼福特算法（求带负权值的单源最短路径）
     * 这个是暴力求解
     * 需要遍历每个节点 查看从节点开始s开始到对应的节点最短的路径
     * @param vSrc 起点
     * @param dist 权值数组
     * @param pPath 关系数组
     * @return false 存在存在负权回路 true 不存在存在负权回路
     */
    public boolean bellmanFord(char vSrc,int[] dist,int[] pPath) {
        int srcIndex = getIndex(vSrc);

        Arrays.fill(dist,Integer.MAX_VALUE);
        dist[srcIndex] = 0;

        Arrays.fill(pPath,-1);
        pPath[srcIndex] = 0;
        int len = arrayV.length;
        for(int k = 0;k < len;k++) {
            for(int i = 0;i < len;i++) {
                for(int j =0;j < len;j++) {
                    if(matrix[i][j] != Integer.MAX_VALUE
                            && dist[i] + matrix[i][j] < dist[j]) {
                        dist[j] = dist[i] + matrix[i][j];
                        pPath[j] = i;
                    }
                }
            }
        }
        for(int i = 0;i < len;i++) {
            for(int j =0;j < len;j++) {
                if(matrix[i][j] != Integer.MAX_VALUE
                        && dist[i] + matrix[i][j] < dist[j]) {
                    return false;
                }
            }
        }
        return true;
    }

    public static void testGraphBellmanFord() {
        String str = "syztx";
        char[] array = str.toCharArray();
        GraphByMatrix g = new GraphByMatrix(str.length(),true);
        g.insertArrayV(array);
        g.addEdge('s', 't', 6);
        g.addEdge('s', 'y', 7);
        g.addEdge('y', 'z', 9);
        g.addEdge('y', 'x', -3);
        g.addEdge('z', 's', 2);
        g.addEdge('z', 'x', 7);
        g.addEdge('t', 'x', 5);
        g.addEdge('t', 'y', 8);
        g.addEdge('t', 'z', -4);
        g.addEdge('x', 't', -2);
        //负权回路实例

//        g.addEdge('s', 't', 6);
//        g.addEdge('s', 'y', 7);
//        g.addEdge('y', 'z', 9);
//        g.addEdge('y', 'x', -3);
//        g.addEdge('y', 's', 1);
//        g.addEdge('z', 's', 2);
//        g.addEdge('z', 'x', 7);
//        g.addEdge('t', 'x', 5);
//        g.addEdge('t', 'y', -8);
//        g.addEdge('t', 'z', -4);
//        g.addEdge('x', 't', -2);

        int[] dist = new int[array.length];
        int[] parentPath = new int[array.length];
        boolean ﬂg = g.bellmanFord('s', dist, parentPath);
        if(ﬂg) {
            g.printShortPath('s', dist, parentPath);
        }else {
            System.out.println("存在负权回路");
        }
    }

    /**
     * 费罗伊德算法（多源最短路径）
     * 求经过从点i 到点 j 是经过k的权值少还是不经过的少，选择少的
     * @param dist 权值矩阵
     * @param pPath 关系矩阵
     */
    public void ﬂoydWarShall(int[][] dist,int[][] pPath) {
        int len = arrayV.length;
        // 初始化两个矩阵
        for(int i =0;i < len;i++) {
            Arrays.fill(dist[i],Integer.MAX_VALUE);
            Arrays.fill(pPath[i],-1);
        }
        // 初始化权值

        for(int i =0; i < len;i++) {
            for(int j =0; j < len;j++) {
                if(matrix[i][j] != Integer.MAX_VALUE) {
                    dist[i][j] = matrix[i][j];
                    pPath[i][j] = i;
                }
                if(i == j) {
                    dist[i][j] = 0;
                    pPath[i][j] = -1;
                }
            }
        }

        // 到这里： dist权值矩阵 和 pPath关系矩阵已经全部初始化完毕
        for(int k = 0; k < len; k++) {
            for(int i = 0; i < len;i++) {
                for(int j =0; j < len; j++) {
                    if(dist[i][k] != Integer.MAX_VALUE
                            && dist[k][j] != Integer.MAX_VALUE
                            && dist[i][k] + dist[k][j] < dist[i][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];// 更新权值
                        pPath[i][j] = pPath[k][j];// 更新父节点
                    }
                }
            }
            // 测试 打印权值和路径矩阵观察数据

            for (int i = 0; i < len; i++) {
                for (int j = 0; j < len; j++) {
                    if(dist[i][j] == Integer.MAX_VALUE) {
                        System.out.print(" * ");
                    }else{
                        System.out.print(dist[i][j]+" ");
                    }
                }
                System.out.println();
            }
            System.out.println("=========打印路径==========");
            for (int i = 0; i < len; i++) {
                for (int j = 0; j < len; j++) {
                    System.out.print(pPath[i][j]+" ");
                }
                System.out.println();
            }
            System.out.println("=================");
        }
    }
    public static void testGraphFloydWarShall() {
        String str = "12345";
        char[] array = str.toCharArray();
        GraphByMatrix g = new GraphByMatrix(str.length(), true);
        g.insertArrayV(array);
        g.addEdge('1', '2', 3);
        g.addEdge('1', '3', 8);
        g.addEdge('1', '5', -4);
        g.addEdge('2', '4', 1);
        g.addEdge('2', '5', 7);
        g.addEdge('3', '2', 4);
        g.addEdge('4', '1', 2);
        g.addEdge('4', '3', -5);
        g.addEdge('5', '4', 6);

        int[][] dist = new int[array.length][array.length];
        int[][] parentPath = new int[array.length][array.length];
        g.ﬂoydWarShall(dist, parentPath);

        for (int i = 0; i < array.length; i++) {
            g.printShortPath(array[i], dist[i], parentPath[i]);
            System.out.println("********************");
        }
    }

    public static void main(String[] args) {
            testGraphFloydWarShall();
    }

    public static void main2(String[] args) {
        GraphByMatrix graph = new GraphByMatrix(4,true);    
        char[] array = {'A','B','C','D'};    
        graph.insertArrayV(array);
        graph.addEdge('A','B',1);   
        graph.addEdge('A','D',1);    
        graph.addEdge('B','A',1);    
        graph.addEdge('B','C',1);    
        graph.addEdge('C','B',1);    
        graph.addEdge('C','D',1);    
        graph.addEdge('D','A',1);    
        graph.addEdge('D','C',1);

        graph.dfs('A');
    }
    public static void main1(String[] args) {
        GraphByMatrix graph = new GraphByMatrix(4, true);
        char[] array = {'A', 'B', 'C', 'D'};
        graph.insertArrayV(array);

        graph.addEdge('A', 'B', 1);
        graph.addEdge('A', 'D', 1);
        graph.addEdge('B', 'A', 1);
        graph.addEdge('B', 'C', 1);
        graph.addEdge('C', 'B', 1);
        graph.addEdge('C', 'D', 1);
        graph.addEdge('D', 'A', 1);
        graph.addEdge('D', 'C', 1);
        System.out.println(graph.getDevOfV('A'));
        graph.printGraph();
    }
}
